#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<Stdbool.h>

void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if (begin >= end)
        return;

    int mid = (begin + end) / 2;
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);

    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = begin;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
    memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* nums, int numsSize)
{
    int* tmp = (int*)malloc(sizeof(int) * numsSize);
    if (tmp == NULL)
    {
        exit(-1);
    }
    int end = numsSize - 1;
    _MergeSort(nums, 0, end, tmp);
    free(tmp);
}
bool containsDuplicate(int* nums, int numsSize) {
    MergeSort(nums, numsSize);
    for (int i = 0; i < numsSize - 1; i++)
    {
        if (nums[i] == nums[i + 1])
            return true;
    }
    return false;
}

//int main()
//{
//    int a[] = { 1,5,8,98,897,89,9,9,9,4,64,6,6,6,6,13,13,1 };
//    MergeSort(a, (sizeof(a) / sizeof(a[0])));
//
//    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
//    {
//        printf("%d ", a[i]);
//    }
//    return 0;
//}